package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/5 16:35
 */
public class GardenNoAdj {

    public static void main(String[] args) {
        GardenNoAdj test = new GardenNoAdj();


        // {1,2,3}
//        int n = 3;
//        int[][] arr= {{1,2},{2,3},{3,1}};

        // {1,2,1,2}
//        int n = 4;
//        int[][] arr = {{1, 2}, {3, 4}};

        // {1,2,3,4}
        int n = 4;
        int[][] arr={{1,2},{2,3},{3,4},{4,1},{1,3},{2,4}};

        int[] ints = test.gardenNoAdj(n, arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] gardenNoAdj(int n, int[][] paths) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] path : paths) {
            map.computeIfAbsent(path[0] - 1, v -> new ArrayList<>()).add(path[1] - 1);
            map.computeIfAbsent(path[1] - 1, v -> new ArrayList<>()).add(path[0] - 1);
        }
        int[] arr = new int[n];
        int[] item = new int[5];
        for (int i = 0; i < n; i++) {
            find(i, arr, map, item);
        }
        return arr;
    }

    private void find(int index, int[] arr, Map<Integer, List<Integer>> map, int[] item) {
        List<Integer> list = map.get(index);
        if (list == null) {
            arr[index] = 1;
            return;
        }
        for (int c : list) {
            item[arr[c]] = 1;
        }
        for (int i = 1; i < 5; i++) {
            if (item[i] == 0) {
                arr[index] = i;
                break;
            }
        }
        Arrays.fill(item, 0);
    }

}
